Digital halftoning is a technique employing digital image processing to produce a halftone output image from a continuous-tone image. For digital halftoning techniques, a continuous-tone input digital image is provided, for example, by scanning an original hardcopy image and storing digitized pixels in a computer. The digitized pixels include discrete digital input values typically ranging from 0 to 255. To reproduce this image on an output device capable of printing dots of one gray level (e.g., black), it is necessary to convert the continuous-tone input digital image to a binary output digital image using some form of digital halftoning algorithm. Halftoning methods rely on the fact that an observer's eye will spatially average over some local area of the image so that the appearance of intermediate gray levels can be produced by turning some of the pixels “on” and some of the pixels “off” in some local image region. The fraction of the pixels that are turned on will determine the apparent gray level. Common prior art methods of digital halftoning include error diffusion and periodic dithering.
Error diffusion is an adaptive algorithm that produces patterns with different spatial frequency content depending on the input image value. FIG. 1 shows a block diagram describing a basic error diffusion technique disclosed in “An Adaptive Algorithm for Spatial Greyscale,” Proceedings of the Society for Information Display, Vol. 17, pp. 75-77, 1976, by R. W. Floyd and L. Steinberg. For purpose of illustration it will be assumed that the continuous-tone input values span the range from 0 to 255. A threshold operator 10 is applied to the input pixel value I(x,y) for the current input pixel with coordinates x and y to form the output pixel value O(x,y). The threshold operator 10 will return a 0 for any continuous-tone input value below the threshold, and a 255 for any continuous-tone input value above the threshold. A difference signal generator 12 receives the input pixel value I(x,y) and the output pixel value O(x,y), and produces an error signal e(x,y) by computing a difference between the output pixel value and the adjusted pixel value representing the error introduced by the thresholding process. The error signal e(x,y) is scaled by a series of error feedback weights W(x,y) using a weighted error signal generator 14, and is provided to an adder 16 which adds the weighted difference signal to the input pixel values of nearby pixels that have yet to be processed to form modified input values. The propagation of the errors made during the thresholding process to the nearby pixels ensures that the arithmetic mean of the pixel values is preserved over a local image region.
FIG. 2 illustrates a typical set of error feedback weights W(x,y) that can be used to distribute the error e(x,y) to the nearby pixels. In this example, 7/16 of the error is propagated to the next pixel on the same row of the image, 5/16 of the error is propagated to the pixel directly below the current pixel on the next row of the image, and so forth. The halftone output from error diffusion is considered to be of high quality generally, since most of the halftone noise is distributed in a high spatial frequency band where human visual sensitivity is relatively low. However, the error diffusion halftoning technique is known to produce a number of objectionable artifacts. One artifact that is typically associated with error diffusion is known as “worms.” Worms are formed when the black or white output pixels appear to string together in an area that should be otherwise uniform.
Compared to the error diffusion technique, ordered dither halftoning techniques are generally simpler in implementation. The ordered dither technique is typically implemented by forming a dither matrix having Mx×My elements that is tiled across the image. The elements of the dither matrix are distributed across the range of expected input tone values so that the full range of tones can be reproduced. A typical ordered dither halftoning method is illustrated in FIG. 3. A given pixel in the image has column and row addresses x and y, respectively, and an input pixel value I(x,y). Modulo operators 20 are used to determine indices xd and yd that are used to address the dither matrix 22. The threshold value d(xd,yd) stored in the dither matrix at this address is then compared to the input pixel value I(x,y) using a comparator 24. If the input pixel value is equal to or below the threshold value, the output pixel value O(x,y) is set to “off”; if the value is above the threshold, the output pixel value O(x,y) is set to “on”.
A second implementation of this basic technique is shown in FIG. 4. In this case the threshold value d(xd,yd) is combined with the input pixel value I(x,y) using an adder 26. A fixed threshold operator 28 is then used to threshold the combined value to determine the output pixel value O(x,y).
Another implementation of this basic technique is shown in FIG. 5. In this case a set of k dither bitmaps 32 are formed corresponding to the halftone patterns formed when the dither matrix is thresholded at each input level k. The input pixel value I(x,y) is then used to select which of the dither bitmaps should be used for each pixel. Modulo operators 30 are used to determine indices xd and yd that are used to address the selected dither bitmap to determine the output pixel value O(x,y). This implementation has the advantage that fewer computations are necessary to process each pixel. It should be noted that any dither pattern that can be implemented using the methods of FIG. 3 and FIG. 4 can also be implemented using the method of FIG. 5. However, it is possible to define a set of dither bitmaps for the method of FIG. 5 that could not be implemented using the other methods. This is because in the dither matrix implementations once a certain pixel is turned on at the input value corresponding to the threshold, it will stay on for all higher input values. With the dither bitmaps approach this constraint is not present. For example, a certain pixel could be “off” for an input value of 150, “on” for an input value of 151, and “off” again for an input value of 152.
Yet another implementation of this basic technique is shown in FIG. 6. In this case a set of dither look-up tables (LUTs) 36 is used. The dither LUTs 36 are addressed by the input pixel value I(x,y) and store the corresponding output pixel value to be produced at some pixel location. Modulo operators 30 are used to determine indices xd and yd that are used to address a dither LUT selector 34 which selects one of the dither LUTs 36. The output pixel value O(x,y) is determined by addressing the selected dither LUT with the input pixel value I(x,y). This implementation also has the advantage that fewer computations are necessary to process each pixel. It should be noted that any dither pattern that can be implemented using the methods of FIG. 3 and FIG. 4 can also be implemented using the method of FIG. 6. However, as with the method shown in FIG. 5, it is also possible to define a set of dither LUTs 36 that could not be implemented using the other methods.
A variety of different dither matrices have been used in the past which produce resulting images with different visual characteristics. Common types include random dither matrices, clustered-dot dither matrices, and Bayer (dispersed dot) dither matrices. Sullivan, et al., U.S. Pat. No. 4,920,501, have introduced a technique to design dither bitmaps that have minimum visual modulation. These patterns are sometimes called “blue noise” patterns. They are attractive in that the patterns that are produced have minimum visibility to human observers, and as a result the images produced are visually pleasing relative to images produced using other dither patterns. The basic procedure involved in the production of these patterns is to use an optimization technique, such as stochastic annealing, to determine the arrangement of the matrix elements that reduces some visual cost function, typically based upon weighting the frequency components of the halftone patterns with a human visual sensitivity function. U.S. Pat. No. 4,920,501 also discloses an enhancement to this method, which insures that the bitmaps for each of the gray levels are correlated in such a way that they can be implemented using a dither matrix, U.S. Pat. No. 5,214,517. Other extensions to this basic approach include a method for simultaneously optimizing all of the gray levels, U.S. Pat. No. 5,754,311, a method for designing blue noise dither matrices for use with multilevel output devices, U.S. Pat. No. 5,586,203, and a method for producing partially correlated dither matrices, U.S. Pat. No. 5,946,452.
Parker, et al., U.S. Pat. No. 5,111,310, and Lin, U.S. Pat. Nos. 5,317,418 and 5,469,515, have also introduced techniques for the design of blue-noise dither patterns. Although the actual optimization methods that they have used are somewhat different, the resulting patterns are quite similar to those produced using the methods described in the Sullivan, et al. patents.
Recently, a wide variety of printing devices with multilevel output (No output levels, where No>2) capability have been brought to the market to achieve higher image quality. Both ordered dither and error diffusion halftoning techniques can be generalized for these devices, in which case the halftoning methods are often referred to as “multi-level halftoning” or “multi-toning.” For example, the conventional error diffusion process shown in FIG. 1 can be generalized to more than two output levels by replacing the threshold operator 10 with a quantization operator that selects one of the available output levels as a function of the modified input levels. Similarly, the ordered dithering technique shown in FIG. 4 can be generalized for more than 2 output levels by replacing the threshold operation 28 by a quantization operation. As before, the periodic dither signal is added to the input pixel value. The quantizer then maps the modulated input pixel value to one of the allowable output levels. In this case, the amplitude of the dither signal is generally scaled to be the same as the size of the quantization interval. Likewise, the ordered dither algorithms shown in FIG. 5 and FIG. 6 can also be generalized to more than 2 output levels by storing the desired multi-level output levels in the dither bitmaps 32 or the dither LUTs 36 rather than the binary output levels used in the 2 level implementations. Rather than storing complete dither LUTs for the multi-level implementation of FIG. 6, it can be desirable to store only the breakpoints where each LUT transitions from one output level to the next in order to reduce memory requirements. In this way, the LUT can be recreated as necessary, or the input value can be directly tested against each of the breakpoints.
FIG. 7 shows a comparison of images produced from a continuous tone gray wedge using several different halftoning algorithms. FIG. 7A shows output produced using a conventional binary error diffusion halftoning algorithm. Worm artifacts can be clearly seen in several areas of the tone scale, such as the light and dark ends of the gray wedge. Several of these worm artifacts are labeled as 70. FIG. 7B shows output produced using a conventional blue-noise dither algorithm. The dither matrix in this example was produced using the method of Sullivan, et al., U.S. Pat. No. 5,214,517. It can be seen that the worm artifacts associated with error diffusion have been limited, but that the overall graininess of the resulting image is somewhat higher than for error diffusion. This increased graininess 71 is particularly apparent in the mid-tone gray values.
FIG. 7C shows output produced using a multi-level error diffusion algorithm with three output levels (No=3). The same characteristic worm artifacts are present that were found in the binary error diffusion case. In addition, it can be observed that an objectionable texture/luminance contour 72 forms in the center of the tone scale near the intermediate output level. FIG. 7D shows output produced using a multi-level blue-noise dither algorithm, again with three output levels (No=3). A texture contour 73 can be observed near the intermediate output level, although it is not as severe as for the multi-level error diffusion case shown in FIG. 7C.
The texture contouring problem can be explained with the following analysis. For input image levels right at the output levels there is no halftone, or multitone, error introduced; therefore, there is no visual modulation necessary to produce the desired gray level. However, if the input level is a few code values away from those output levels, the output halftone pattern is rendered with sparse minority pixels over a uniform majority-pixel background. Since human visual system is very sensitive to these kinds of dot patterns, the perceived “grain” is much higher. Therefore, if a continuous-tone input image contains a smooth transition across this range of input levels, then, with the conventional multitoning approaches, there will be a distinct texture change in the output image which is observed as texture contouring within certain viewing distances.
Yu, et al. introduced an approach to smooth the texture transition at the N output levels for multilevel blue-noise dithering using over-modulated dither patterns in “Digital Multitoning Evaluation with a Human Visual Model,” IS&T's NIP13: International Conference on Digital Printing Technologies, 579-585 (1997). Special blue-noise dither matrices were designed to precisely control the texture of the over-modulated patterns near the N output levels. It was found that over-modulated patterns resulting from a “binar” dither matrix were preferred by human observers over those from other dither matrices. The “binar” dither matrix is so named since its large dither matrix elements are paired with, and arranged to be adjacent to, its small dither matrix elements. An example of the over-modulation patterns from a “binar” dither matrix is shown in FIG. 8, where pixels of lower output level 80 and pixels of higher output level 81 are introduced in pairs within an otherwise uniform input image whose pixel values are equal to an intermediate output level 82.
Yu, et al. have extended the dither over-modulation approach to address the contouring artifacts associated with the multi-level error diffusion algorithm in U.S. Pat. No. 6,271,936. With this method, a blue-noise dither signal is added to the input pixel values for gray levels near the No output levels. This has the effect of introducing over-modulated blue noise patterns at transition levels, limiting the undesirable texture contouring artifacts shown in FIG. 7C, while maintaining the lower granularity of the multi-level error diffusion algorithm at gray levels intermediate to the output levels. FIG. 7E shows output produced using the hybrid multi-level dither/error diffusion algorithm with three output levels (No=3). While this method does substantially reduce texture contouring near the output levels, which is one of the most objectionable artifacts associated with multi-level error diffusion, it does not address the worm artifacts that are characteristic of error diffusion. These worm artifacts can still be seen in FIG. 7E where a number of them are labeled as 74.
“An Improved Multilevel Error Diffusion Method,” Journal of Imaging Science and Technology, Vol. 39, No. 6, pp. 495-501, 1995, by S. Sugiura, et al. discloses adding noise using a 4 by 4 ordered dither matrix for a wide range of input pixel values around the N output levels, thus limiting the texture contouring at the N output levels for multilevel error diffusion. However, this is at the expense of increased halftone visibility over a wide range of the tone scale, and the interaction between ordered dither matrix and error diffusion could result in artifacts due to the lack of precise control of halftone patterns around the N output levels.
Metcalfe, et al., U.S. Pat. No. 6,449,061, disclose a way for reducing “pattern shifting artifacts” in an error diffusion algorithm by adding random noise, or patterned noise to the error diffusion threshold value. The amplitude of the noise is adjusted according to an image classification of the pixel being processed. This approach has the disadvantage that the noise that is being introduced is quite dissimilar to the noise characteristics of the error diffusion process, and therefore is not well-suited to producing consistent texture characteristics across the tone scale. It also requires an image classification step that can be quite complex.